Blum Blum Shub

Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
__TOC__
Blum Blum Shub takes the form

:$x_ = x_n^2 \bmod M$,

where ''M'' = ''pq'' is the product of two large primes ''p'' and ''q''. At each step of the algorithm, some output is derived from ''x''_''n''+1; the output is commonly either the bit parity of ''x''_''n''+1 or one or more of the least significant bits of ''x''_''n''+1''.

The seed ''x''₀ should be an integer that is co-prime to ''M'' (i.e. ''p'' and ''q'' are not factors of ''x''₀) and not 1 or 0.

The two primes, ''p'' and ''q'', should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue), and should be safe primes with a small gcd((''p-3'')''/2'', (''q-3'')''/2'') (this makes the cycle length large).

An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any ''x''_''i'' value directly (via Euler's theorem):

:$x_i = \left( x_0^ \right) \bmod M$,

where $\lambda$ is the Carmichael function. (Here we have $\lambda(M) = \lambda(p\cdot q) = \operatorname(p-1, q-1)$).

Security

There is a proof reducing its security to the computational difficulty of factoring. When the primes are chosen appropriately, and ''O''(log log ''M'') lower-order bits of each ''x_n'' are output, then in the limit as ''M'' grows large, distinguishing the output bits from random should be at least as difficult as solving the quadratic residuosity problem modulo ''M''.

Example

Let $p=11$, $q=23$ and $s=3$ (where $s$ is the seed). We can expect to get a large cycle length for those small numbers, because $((p-3)/2, (q-3)/2)=2$.
The generator starts to evaluate $x_0$ by using $x_=s$ and creates the sequence $x_0$, $x_1$, $x_2$, $\ldots$ $x_5$ = 9, 81, 236, 36, 31, 202. The following table shows the output (in bits) for the different bit selection methods used to determine the output.

The following Common Lisp implementation provides a simple demonstration of the generator, in particular regarding the three bit selection methods. It is important to note that the requirements imposed upon the parameters ''p'', ''q'' and ''s'' (seed) are not checked.

(defun get-number-of-1-bits (bits)
"Returns the number of 1-valued bits in the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the (integer 0 *) (logcount bits)))

(defun get-even-parity-bit (bits)
"Returns the even parity bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (mod (get-number-of-1-bits bits) 2)))

(defun get-least-significant-bit (bits)
"Returns the least significant bit of the integer-encoded BITS."
(declare (type (integer 0 *) bits))
(the bit (ldb (byte 1 0) bits)))

(defun make-blum-blum-shub (&key (p 11) (q 23) (s 3))
"Returns a function of no arguments which represents a simple
Blum-Blum-Shub pseudorandom number generator, configured to use the
generator parameters P, Q, and S (seed), and returning three values:
(1) the number x +1
(2) the even parity bit of the number,
(3) the least significant bit of the number.
---
Please note that the parameters P, Q, and S are not checked in
accordance to the conditions described in the article."
(declare (type (integer 0 *) p q s))
(let ((M (* p q)) ;; M = p * q
(x s)) ;; x0 = seed
(declare (type (integer 0 *) M x )
#'(lambda ()
;; x +1= x 2 mod M
(let ((x +1(mod (* x x M)))
(declare (type (integer 0 *) x +1)
;; Compute the random bit(s) based on x +1
(let ((even-parity-bit (get-even-parity-bit x +1)
(least-significant-bit (get-least-significant-bit x +1))
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
;; Update the state such that x +1becomes the new x
(setf x x +1
(values x +1 even-parity-bit
least-significant-bit))))))

;; Print the exemplary outputs.
(let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3)))
(declare (type (function () (values (integer 0 *) bit bit)) bbs))
(format T "~&Keys: E = even parity, L = least significant")
(format T "~2%")
(format T "~&x +1, E , L")
(format T "~&--------------")
(loop repeat 6 do
(multiple-value-bind (x +1even-parity-bit least-significant-bit)
(funcall bbs)
(declare (type (integer 0 *) x +1)
(declare (type bit even-parity-bit))
(declare (type bit least-significant-bit))
(format T "~&~6d , ~d , ~d"
x +1even-parity-bit least-significant-bit))))

References

Citations

Sources

*
*
*
{{refend

External links

GMPBBS, a C-language implementation by Mark Rossmiller

BlumBlumShub, a Java-language implementation by Mark Rossmiller

An implementation in Java

Randomness tests

Pseudorandom number generators
Cryptographically secure pseudorandom number generators